﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class BubbleSortWithReversals
{
    public int getMinSwaps(int[] A, int K)
    {
        int[] sortedA = A.OrderBy(p=>p).ToArray();

        Dictionary<int, int> lPos = new Dictionary<int, int>();
        Dictionary<int, int> rPos = new Dictionary<int, int>();
        for (int i = 0; i < A.Length; i++)
        {
            int num = sortedA[i];
            if (!lPos.ContainsKey(num)) lPos[num] = i;
            rPos[num]=i;
        }

        int[] diffA = new int[A.Length];
        for (int i = 0; i < A.Length; i++)
        {
            int num = A[i];
            if (lPos[num] <= num && num <= rPos[num])
            {
                diffA[i] = 0;
            }
            else if (num < lPos[num])
            {
                diffA[i] = lPos[num] - i;
            }
            else if (rPos[num] < num)
            {
                diffA[i] = rPos[num] - i;
            }
        }

        int[,] diffR = new int[A.Length, A.Length]; 
        for (int i = 0; i < A.Length; i++)
        {
            for (int j = i + 1; j < A.Length; j++)
            {
                for (int k = i; k <= j; k++)
                {
                    if (diffA[k] > 0)
                    {
                        diffR[i, j] += diffA[k]-j+k;
                    }
                }
            }
        }


        return 0;
    }
}
 

public class ManySquares
{
    public int howManySquares(int[] sticks)
    {
        Dictionary<int, int> lenCnt = new Dictionary<int, int>();
        foreach (int len in sticks)
        {
            if (!lenCnt.ContainsKey(len)) lenCnt[len] = 0;
            lenCnt[len]++;
        }

        int square = 0;
        foreach (var kv in lenCnt)
        {
            square += kv.Value / 4;
        }

        return square;
    }
}

public class HappyLetterDiv2
{
    public char getHappyLetter(string letters)
	{
        var max = letters.GroupBy(p => p).Aggregate((l, r) => l.Count() > r.Count() ? l : r);
        return (max.Count() > letters.Length - max.Count()) ? max.Key : '.';

        //char[] arr = letters.ToCharArray();
        //Dictionary<char, int> charCnt = new Dictionary<char,int>();
        //foreach (char c in arr)
        //{
        //    if (!charCnt.ContainsKey(c)) charCnt[c] = 0;
        //    charCnt[c]++;
        //}

        //char maxChar = charCnt.OrderByDescending(p => p.Value).First().Key;
        //int max = charCnt[maxChar];
      
        //if (max > arr.Length - max) return maxChar;
        //else return '.';

    }

}